package org.example.linkedList;

import org.junit.Before;
import org.junit.Test;

import java.util.Random;

/**
 * @Auther: wangbw
 * @Date:2020/12/14
 * @Description: org.example.linkedList
 * @version: 1.0
 */
public class ReservoirSamplingTest {
    private final int N = 100000;
    private int[] pool;
    private Random random = new Random();

    @Before
    public void setUp() {
        pool = new int[N];
        for (int i = 0; i < N; i++) {
            pool[i] = i;
        }
    }

    public int[] sampling(int k) {
        int[] randomPool = new int[k];
        for (int i = 0; i < k; i++) {
            randomPool[i] = pool[i];
        }

        for (int i = k; i < N; i++) {
            int temp = random.nextInt(i + 1);
            if (temp < k) {
                randomPool[temp] = pool[i];
            }
        }
        return randomPool;
    }

    @Test
    public void test() {
        for (int i : sampling(20)) {
            System.out.print(i + "\t");
        }
    }
}
/**
 * 96901	94466	47745	11404	92468	39262	45366	40510	25899	89419	17309	16858	2271	49870
 * 92762	43886	3564	1007	73050	32270
 */